﻿using PhraseCorrector.Common;
using PhraseCorrector.DirectTanslate;
using PhraseCorrector.SpellCore;
using PhraseCorrector.SpellCorrect;
using PhraseCorrector.WordLineSplit;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

namespace PhraseCorrector.SpellLook
{
    public partial class Spell
    {
        #region Fields
        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 默认的最大编辑距离，用于字符串相似度计算
        const int defaultMaxEditDistance = 2;
        // 默认的前缀长度，用于加速字符串匹配
        const int defaultPrefixLength = 7;
        // 默认的计数阈值，用于过滤低频元素
        const int defaultCountThreshold = 1;
        // 默认的紧凑级别，用于优化内存占用
        const int defaultCompactLevel = 0;
        // 默认的分隔字符数组，用于字符串分割，null值表示不使用分隔字符
        const char[] defaultSeparatorChars = null;
        /// <summary>
        /// 匹配过滤器，用于过滤掉非单词字符。
        /// </summary>
        public static readonly Regex Filter = new Regex(@"['’\w-[_]]+", RegexOptions.Compiled);

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 紧凑掩码，用于优化内存占用。
        /// </summary>
        private uint compactMask { set; get; }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 编辑距离算法，默认使用Damerau-Osa算法。
        /// </summary>
        private EditDistance.DistanceAlgorithm distanceAlgorithm { set; get; } = EditDistance.DistanceAlgorithm.Levenshtein;

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        ///  包含未达到正确拼写计数阈值的唯一单词及其计数的字典。
        /// </summary>
        private Dictionary<string, long> belowThresholdWords { set; get; } = new Dictionary<string, long>();

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 最大编辑距离，
        /// 用于限定字符串相似度计算的最大值。
        /// 用于字典预计算的最大编辑距离。
        /// </summary>
        private int maxDictionaryEditDistance { set; get; }
        public int MaxDictionaryEditDistance { get { return maxDictionaryEditDistance; } }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 前缀长度，用于加速字符串匹配，通常在5到7之间。
        /// </summary>
        private int prefixLength { set; get; }
        /// <summary>
        /// 生成删除操作的前缀长度。
        /// </summary>
        public int PrefixLength { get { return prefixLength; } }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 字典中最长词的长度。 是创建字典时自动统计的结果
        /// </summary>
        private int maxDictionaryWordLength { set; get; }
        public int MaxLength { get { return maxDictionaryWordLength; } }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 计数阈值，用于确定一个词是否频繁出现到足以被认为是拼写纠正的有效词。
        /// </summary>
        private long countThreshold { set; get; }
        public long CountThreshold { get { return countThreshold; } }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 存储唯一正确拼写的单词及其计数的字典。
        /// </summary>
        public Dictionary<string, long> Wordlibrary { set; get; } = new Dictionary<string, long>();

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 字典中的唯一单词数量。
        /// </summary>
        public int WordCount { get { return Wordlibrary.Count; } }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 存储建议修正词列表到原始词及其删除序列哈希值映射的字典。
        /// 允许哈希值碰撞，因为最终会通过编辑距离函数验证建议。
        /// 建议列表可能包含单个建议或多个建议。
        /// </summary>
        public Dictionary<int, string[]> deletes { set; get; } = new Dictionary<int, string[]>();

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 字典中编码的单词前缀和中间删除操作的数量。
        /// </summary>
        public int EntryCount { get { return deletes.Count; } }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 默认的最大编辑距离，用于字符串相似度计算
        /// <summary>
        /// 语言模型。
        /// </summary>
        public PhraseType LanguageModel { get; set; } = PhraseType.None;

        #endregion

        #region 构造函数
        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 创建一个新的 SymSpell 实例。
        /// </summary>
        /// <remarks>
        /// 指定准确的初始容量不是必需的，但可以帮助通过避免随着大小增长而需要的数据重组来加快处理速度。
        /// </remarks>
        /// <param name="maxDictionaryEditDistance">进行查找的最大编辑距离。</param>
        /// <param name="prefixLength">用于拼写检查的单词前缀长度。</param>
        /// <param name="countThreshold">字典单词被视为正确拼写的最小频率计数。</param>
        /// <param name="compactLevel">偏向较低内存使用而不是速度的程度（0=最快，最多内存，16=最慢，最少内存）。</param>
        public Spell(
            PhraseType model,
            int maxDictionaryEditDistance = defaultMaxEditDistance,
            int prefixLength = defaultPrefixLength,
            int countThreshold = defaultCountThreshold,
            byte compactLevel = defaultCompactLevel)
        {
            LanguageModel = model;
            ThrowError(maxDictionaryEditDistance, prefixLength, countThreshold, compactLevel);
            Init(maxDictionaryEditDistance, prefixLength, countThreshold, compactLevel);
        }
        #endregion

        #region 创建字典行

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 在字典中创建或更新一个条目。
        /// </summary>
        /// <remarks>
        /// 对于每个单词，都会创建并添加到字典中具有编辑距离 1 到 maxEditDistance 的删除项。
        /// 每个删除项都有一个建议列表，指向它创建的原始术语。可以通过调用 CreateDictionaryEntry 随时动态更新字典（单词频率和新单词）。
        /// </remarks>
        /// <param name="key">要添加到字典中的单词。</param>
        /// <param name="count">单词的频率计数。</param>
        /// <param name="staging">可选的暂存对象，通过将它们暂存到临时结构来加快添加多个条目的速度。</param>
        /// <returns>
        /// 如果单词作为新的正确拼写的单词被添加，则返回 true；
        /// 否则，如果单词作为低于阈值的单词被添加或更新现有的正确拼写的单词，则返回 false。
        /// </returns>
        public bool CreateDictionaryEntry(string key, long count, SuggestionStage staging = null)
        {
            if (count <= 0)
            {
                if (countThreshold > 0) return false; // 如果计数为零，则无需做任何事情，因为它不会改变任何东西
                count = 0;
            }
            long countPrevious = -1;

            // 首先在低于阈值的单词中查找，更新计数，并允许在计数达到阈值时提升为正确拼写的单词
            if (countThreshold > 1 && belowThresholdWords.TryGetValue(key, out countPrevious))
            {
                // 计算低于阈值单词的新计数
                count = long.MaxValue - countPrevious > count ? countPrevious + count : long.MaxValue;
                // 已达到阈值 - 从低于阈值集合中移除（它将在下面添加到正确的单词中）
                if (count >= countThreshold)
                    belowThresholdWords.Remove(key);
                else
                {
                    belowThresholdWords[key] = count;
                    return false;
                }
            }
            else if (Wordlibrary.TryGetValue(key, out countPrevious))
            {
                // 如果是已添加的高于阈值的单词，只需更新计数
                count = long.MaxValue - countPrevious > count ? countPrevious + count : long.MaxValue;
                Wordlibrary[key] = count;
                return false;
            }
            else if (count < CountThreshold)
            {
                // 新的或现有的低于阈值的单词
                belowThresholdWords[key] = count;
                return false;
            }

            // 此时我们有一个新的高于阈值的单词
            Wordlibrary.Add(key, count);

            // 编辑/建议仅创建一次，无论单词出现多少次
            // 编辑/建议仅在单词出现在语料库中时创建，
            // 即使字典中以前存在来自其他单词的编辑
            if (key.Length > maxDictionaryWordLength) {
                if (key.Length < 38) {
                    maxDictionaryWordLength = key.Length;
                }

            }

            deletes ??= new Dictionary<int, string[]>(); // 初始化

            // 创建删除项
            var edits = EditsPrefix(key);
            // 如果不暂存建议，则直接放入主数据结构
            if (staging != null)
                foreach (string delete in edits) staging.Add(GetStringHash(delete), key);
            else
                foreach (string delete in edits)
                {
                    int deleteHash = GetStringHash(delete);
                    if (deletes.TryGetValue(deleteHash, out string[] suggestions))
                    {
                        var newSuggestions = new string[suggestions.Length + 1];
                        Array.Copy(suggestions, newSuggestions, suggestions.Length);
                        deletes[deleteHash] = suggestions = newSuggestions;
                    }
                    else
                    {
                        suggestions = new string[1];
                        deletes.Add(deleteHash, suggestions);
                    }
                    suggestions[suggestions.Length - 1] = key;
                }
            return true;
        }

        #endregion

        #region 装载正常字典
        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 默认的最大编辑距离，用于字符串相似度计算
        /// <summary>
        /// 从包含单词及其频率计数对的文件中加载多个字典条目。
        /// </summary>
        /// <remarks>
        /// 与已加载的任何字典数据合并。
        /// </remarks>
        /// <param name="corpus">文件的路径加文件名。</param>
        /// <param name="termIndex">单词所在的列位置。</param>
        /// <param name="countIndex">频率计数所在的列位置。</param>
        /// <param name="separatorChars">单词和计数之间的分隔字符。</param>
        /// <returns>如果文件加载成功返回 true，否则如果文件未找到返回 false。</returns>
        public bool LoadDictionary(string corpus, int termIndex, int countIndex, char[] separatorChars = defaultSeparatorChars)
        {
            if (!File.Exists(corpus)) return false;
            using (Stream corpusStream = File.OpenRead(corpus))
            {
                return LoadDictionary(corpusStream, termIndex, countIndex, separatorChars);
            }
        }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 默认的最大编辑距离，用于字符串相似度计算
        /// <summary>
        /// 从包含单词及其频率计数对的流中加载多个字典条目。
        /// </summary>
        /// <remarks>
        /// 与已加载的任何字典数据合并。
        /// 术语词汇键使用术语分隔符（默认为'_'）进行分割。
        /// </remarks>
        /// <param name="corpusStream">包含单词及其频率计数对的流。</param>
        /// <param name="termIndex">单词所在的列位置。</param>
        /// <param name="countIndex">频率计数所在的列位置。</param>
        /// <param name="separatorChars">单词和计数之间的分隔字符。</param>
        /// <returns>如果流加载成功返回 true。</returns>
        private bool LoadDictionary(Stream corpusStream, int termIndex, int countIndex, char[] separatorChars = defaultSeparatorChars)
        {
            var staging = new SuggestionStage(16384);

            //加载专用字典
            if (LanguageModel == PhraseType.Chinese)
                LoadChinieseDictionary(termIndex, countIndex, separatorChars);
            else
                LoadEnglishDictionary(termIndex, countIndex, separatorChars);

            // 从文件加载基础字典及其频率
            if (BasePath.DicsModel == LibraryType.All)
                using (StreamReader sr = new StreamReader(corpusStream))
                {
                    string line;
                    // 每次处理一行以提高内存效率
                    while ((line = sr.ReadLine()) != null)
                    {
                        string[] lineParts = line.Split(separatorChars);
                        if (lineParts.Length >= 2)
                        {
                            string key = lineParts[termIndex];
                            if (long.TryParse(lineParts[countIndex], out long count))
                            {
                                if (LanguageModel == PhraseType.Chinese && Utilities.IsChineseBegin(key))
                                    CreateDictionaryEntry(key.Replace("_", " "), count, staging);
                                else
                                    CreateDictionaryEntry(key.Replace("_", " "), count, staging);
                            }
                        }
                    }
                }

            deletes ??= new Dictionary<int, string[]>(staging.DeleteCount);
            CommitStaged(staging);
            return true;
        }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 加载英语词典到应用程序的字典管理器。
        /// </summary>
        /// <param name="termIndex">此参数未使用，保留以满足接口需求。</param>
        /// <param name="countIndex">此参数未使用，保留以满足接口需求。</param>
        /// <param name="separatorChars">用于分割单词的字符数组，默认使用空格和逗号。</param>
        /// <returns>总是返回true，表示英语词典加载成功。</returns>
        public bool LoadEnglishDictionary(int termIndex, int countIndex, char[] separatorChars = defaultSeparatorChars)
        {
            // 初始化建议阶段对象，设定初始容量为16384
            var staging = new SuggestionStage(16384);

            // 每次处理一行以提高内存效率
            foreach (var line in EnglishTraslator.EClibrary)
            {
                // 如果当前行的值非空，则创建字典条目
                if (line.Value.Length > 0)
                    CreateDictionaryEntry(line.Key, 1000, staging);
            }
            // 初始化删除字典，如果未初始化则进行初始化
            deletes ??= new Dictionary<int, string[]>(staging.DeleteCount);
            // 提交建议阶段的更改
            CommitStaged(staging);
            // 总是返回true表示加载成功
            return true;
        }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 加载中文词典到建议阶段，并提交更改。
        /// </summary>
        /// <param name="termIndex">未使用，保留参数，表示词条索引。</param>
        /// <param name="countIndex">未使用，保留参数，表示计数索引。</param>
        /// <param name="separatorChars">分隔符字符数组，用于分割词条，默认使用默认分隔符。</param>
        /// <returns>总是返回true，表示词典加载成功。</returns>
        public bool LoadChinieseDictionary(int termIndex, int countIndex, char[] separatorChars = defaultSeparatorChars)
        {
            // 初始化建议阶段对象，设定初始容量为16384
            var staging = new SuggestionStage(16384);
            // 每次处理一行以提高内存效率
            foreach (var line in ChineseTraslator.CElibrary)
            {
                // 如果当前行的值非空，则创建字典条目
                if (line.Value.Length > 0)
                    CreateDictionaryEntry(line.Key, 1000, staging);
            }
            // 初始化删除字典，如果未初始化则进行初始化
            deletes ??= new Dictionary<int, string[]>(staging.DeleteCount);
            // 提交建议阶段的更改
            CommitStaged(staging);
            // 总是返回true表示加载成功
            return true;
        }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 加载拼音字典到建议阶段
        /// </summary>
        /// <param name="termIndex">未使用</param>
        /// <param name="countIndex">未使用</param>
        /// <param name="separatorChars">分隔符字符数组，默认使用默认分隔符</param>
        /// <returns>总是返回true</returns>
        public bool LoadPinyinDictionary(int termIndex, int countIndex, char[] separatorChars = defaultSeparatorChars)
        {
            // 初始化建议阶段对象，设定初始容量为16384
            var staging = new SuggestionStage(16384);
            // 每次处理一行以提高内存效率
            foreach (var line in PinyinTranslator.PinyinDict)
            {
                // 如果当前行的值非空，则创建字典条目
                if (line.Value.Length > 0 && !string.IsNullOrWhiteSpace(line.Value))
                    CreateDictionaryEntry(line.Key, 1000, staging);
            }
            // 初始化删除字典，如果未初始化则进行初始化
            deletes ??= new Dictionary<int, string[]>(staging.DeleteCount);
            // 提交建议阶段的更改
            CommitStaged(staging);
            // 总是返回true表示加载成功
            return true;
        }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 默认的最大编辑距离，用于字符串相似度计算
        /// <summary>
        /// 提交暂存的字典添加操作。
        /// </summary>
        /// <remarks>
        /// 当您编写自己的过程将多个单词加载到字典中，并且作为该过程的一部分，首先创建了一个 SuggestionStage 对象，并将其传递给 CreateDictionaryEntry 调用时使用。
        /// </remarks>
        /// <param name="staging">存储暂存数据的 SuggestionStage 对象。</param>
        public void CommitStaged(SuggestionStage staging)
        {
            staging.CommitTo(deletes);
        }
        #endregion

        #region LookUp
        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 默认的最大编辑距离，用于字符串相似度计算
        /// <summary>
        /// 查找给定输入单词的建议拼写，使用在构建 SymSpell 字典时指定的最大编辑距离。
        /// </summary>
        /// <param name="input">正在检查拼写的单词。</param>
        /// <param name="verbosity">控制返回建议的数量/接近程度的值。</param>
        /// <returns>
        /// 一个 SuggestItem 对象列表，表示输入单词的建议正确拼写，按编辑距离排序，其次按计数频率排序。
        /// </returns>
        public List<SuggestItem> Lookup(string input, Verbosity verbosity)
        {
            return Lookup(input, verbosity, maxDictionaryEditDistance);
        }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 默认的最大编辑距离，用于字符串相似度计算
        /// <summary>
        /// 查找给定输入单词的建议拼写。
        /// </summary>
        /// <remarks>
        /// verbosity=Top: 返回具有最高词频的最小编辑距离建议
        /// verbosity=Closest: 返回所有最小编辑距离的建议，并按词频排序
        /// verbosity=Similary: 返回所有 <= maxEditDistance 中相似度最高的建议。
        /// verbosity=All: 返回所有 <= maxEditDistance 的建议，并按编辑距离和词频排序（较慢，无提前终止）
        /// </remarks>
        /// <returns>
        /// <param name="input">正在检查拼写的单词。</param>
        /// <param name="verbosity">控制返回建议数量和接近程度的值。</param>
        /// <param name="maxEditDistance">输入单词与建议单词之间的最大编辑距离。</param>
        /// 一个 SuggestItem 对象列表，表示输入单词的建议正确拼写，按编辑距离排序，其次按计数频率排序。
        /// </returns>
        public List<SuggestItem> Lookup(string input, Verbosity verbosity, int maxEditDistance)
        {
            List<SuggestItem> suggestions = new List<SuggestItem>();

            // maxEditDistance 在 Lookup 中不能大于用于构建底层字典结构的最大编辑距离 maxDictionaryEditDistance
            if (maxEditDistance > MaxDictionaryEditDistance)
                maxDictionaryEditDistance = maxEditDistance + 1;

            int inputLen = input.Length;
            // 快速退出 - 单词太大，不可能匹配任何单词
            if (inputLen - maxEditDistance > maxDictionaryWordLength) return suggestions;

            // 快速查找完全匹配, 找到则立即返回
            if (Wordlibrary.TryGetValue(input, out long suggestionCount))
            {
                suggestions.Add(new SuggestItem(input, 0, suggestionCount, 1));
                return suggestions;
            }

            // 提前终止，如果我们只想检查单词是否在字典中或获取其频率，例如用于词分割
            if (maxEditDistance == 0) return suggestions;

            // 已经考虑过的删除操作
            HashSet<string> hashset1 = new HashSet<string>();

            // 已经考虑过的建议, input已经在上面的 words.TryGetValue 中考虑了输入
            HashSet<string> hashset2 = new HashSet<string>() {
                input
            };


            int maxEditDistance2 = maxEditDistance;
            int candidatePointer = 0;
            List<string> candidates = new List<string>();
            // 创建编辑距离比较器
            var distanceComparer = new EditDistance(distanceAlgorithm);


            // 添加原始前缀
            int inputPrefixLen = inputLen;
            if (inputPrefixLen > prefixLength)
            {
                inputPrefixLen = prefixLength;
                candidates.Add(input.Substring(0, inputPrefixLen));
            }
            else
            {
                candidates.Add(input);
            }

            while (candidatePointer < candidates.Count)
            {
                string candidate = candidates[candidatePointer++];
                int candidateLen = candidate.Length;
                int lengthDiff = inputPrefixLen - candidateLen;

                // 节省时间 - 提前终止
                // 如果候选词的编辑距离已经大于建议的最大编辑距离，则不会有更好的建议
                if (lengthDiff > maxEditDistance2)
                {
                    // 如果是 Verbosity.All，则跳到下一个候选词；
                    // 如果是 Verbosity.Top 或 Closest，则不再查找（候选词按删除距离排序，所以没有比当前更近的）
                    if (verbosity == Verbosity.All || verbosity == Verbosity.Similarity) continue;
                    break;
                }
                // 从字典中读取候选条目
                if (deletes.TryGetValue(GetStringHash(candidate), out string[] dictSuggestions))
                {
                    // 遍历删除项的建议（指向其他正确的字典项）并将其添加到建议列表中
                    for ( int i = 0; i < dictSuggestions.Length; i++)
                    {

                        var suggestion = dictSuggestions[i];
                        int suggestionLen = suggestion.Length;
                        if (suggestion == input) continue;

                        if (
                            Math.Abs(suggestionLen - inputLen) > maxEditDistance2 // 输入和建议长度差大于允许的最大编辑距离
                            || suggestionLen < candidateLen // 建议必须对应不同的删除字符串，仅因为哈希冲突在同一桶中
                            || suggestionLen == candidateLen && suggestion != candidate // 如果建议长度等于删除长度，则要么相等，要么仅因哈希冲突在同一桶中
                        )
                            continue;

                        // 如果建议长度大于输入长度，则它必须至少与输入相同长度的前缀匹配
                        var suggPrefixLen = Math.Min(suggestionLen, prefixLength);
                        if (suggPrefixLen > inputPrefixLen && suggPrefixLen - candidateLen > maxEditDistance2) continue;

                        // 真实的 Damerau-Levenshtein 编辑距离：调整距离，如果两者距离均大于 0
                        // 允许同时在字典项和输入项上进行最大编辑距离的删除操作。
                        // 对于替换和相邻位置的交换，结果编辑距离仍 <= maxEditDistance。
                        // 对于插入和删除，结果编辑距离可能超过 maxEditDistance。
                        // 为了防止更高编辑距离的建议，需要计算双方同时编辑后的结果编辑距离。
                        // 示例：(bank==bnak 和 bank==bink，但 bank!=kanb 和 bank!=xban 以及 bank!=baxn 对于 maxEditDistance=1)
                        // 双方各有两个删除操作时它们相等，但前两个对的编辑距离为 1，其他对的编辑距离为 2。
                        int distance = 0;
                        double similary = 0;
                        int min = 0;
                        if (candidateLen == 0)
                        {
                            // 没有与输入共同字符的建议（inputLen<=maxEditDistance && suggestionLen<=maxEditDistance）
                            distance = Math.Max(inputLen, suggestionLen);
                            if (distance > maxEditDistance2 || !hashset2.Add(suggestion)) continue;
                        }
                        else if (suggestionLen == 1)
                        {
                            if (input.IndexOf(suggestion[0]) < 0) distance = inputLen; else distance = inputLen - 1;
                            if (distance > maxEditDistance2 || !hashset2.Add(suggestion)) continue;
                        }
                        else
                        {
                            // 前缀中的编辑次数等于 maxEditDistance 且后缀不相同，则编辑距离 > maxEditDistance，无需计算 Levenshtein
                            if (prefixLength - maxEditDistance == candidateLen
                                && (min = Math.Min(inputLen, suggestionLen) - prefixLength) > 1
                                    && input.Substring(inputLen + 1 - min) != suggestion.Substring(suggestionLen + 1 - min)
                                   || min > 0 && input[inputLen - min] != suggestion[suggestionLen - min]
                                       && (input[inputLen - min - 1] != suggestion[suggestionLen - min]
                                           || input[inputLen - min] != suggestion[suggestionLen - min - 1]))
                            {
                                continue;
                            }
                            else
                            {
                                // DeleteInSuggestionPrefix 比较昂贵，只有当 verbosity 为 Top 或 Closest 时才有意义。
                                if (verbosity != Verbosity.All && verbosity != Verbosity.Similarity && !DeleteInSuggestionPrefix(candidate, candidateLen, suggestion, suggestionLen)
                                    || !hashset2.Add(suggestion)) continue;
                                (distance,similary) = distanceComparer.Distance(input, suggestion);
                                if (distance < 0) continue;
                            }
                        }


                        // 节省时间
                        // 如果 verbosity 不为 All/similary，则不处理比已找到的距离更大的距离（注意：当 Verbosity 为 All/similary 时，maxEditDistance2 总是等于 maxEditDistance）
                        if (distance <= maxEditDistance2) {

                            // 节省时间,如果两词义相似度太低（小于30%），则跳过
                            if (similary < 0.3 || suggestions.Count >0 && suggestions[0].score>similary || suggestion.Length < input.Length-1 )
                                continue;

                            suggestionCount = Wordlibrary[suggestion];
                            SuggestItem si = new SuggestItem(suggestion, distance, suggestionCount, similary);

                            if (suggestions.Count > 0) {
                                switch (verbosity) {
                                    case Verbosity.Similarity:
                                            suggestions.Clear();
                                        break;
                                    case Verbosity.Closest: {
                                            // 只计算到目前为止找到的最小距离的 Damerau-Levenshtein 距离
                                            if (distance < maxEditDistance2) suggestions.Clear();
                                            break;
                                        }
                                    case Verbosity.Top: {
                                            if (distance < maxEditDistance2 || suggestionCount > suggestions[0].count) {
                                                maxEditDistance2 = distance;
                                                suggestions[0] = si;
                                            }
                                            continue;
                                        }
                                }
                            }
                            if (verbosity != Verbosity.All && verbosity != Verbosity.Similarity) maxEditDistance2 = distance;

                            suggestions.Add(si);
                        }
                    }//end foreach
                }//end if         

                // 添加编辑操作
                // 从候选词（输入词）派生编辑操作（删除操作）并将其添加到候选列表中
                // 这是一个递归过程，直到达到最大编辑距离

                if (lengthDiff < maxEditDistance && candidateLen <= prefixLength)
                {
                    // 节省时间
                    // 不创建编辑距离小于已找到建议的编辑操作
                    if (verbosity != Verbosity.All && verbosity != Verbosity.Similarity && lengthDiff >= maxEditDistance2) continue;

                    for (int i = 0; i < candidateLen; i++)
                    {
                        string delete = candidate.Remove(i, 1);

                        if (hashset1.Add(delete)) { candidates.Add(delete); }
                    }
                }
            }//end while

            // 按编辑距离升序排序，然后按词频降序排序
            if (suggestions.Count > 1) suggestions.Sort();

            return suggestions;
        }         

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 默认的最大编辑距离，用于字符串相似度计算
        /// <summary>
        /// 检查所有删除的字符是否按正确顺序出现在建议词的前缀中，否则这只是一个哈希冲突
        /// </summary>
        /// <param name="delete"></param>
        /// <param name="deleteLen"></param>
        /// <param name="suggestion"></param>
        /// <param name="suggestionLen"></param>
        /// <returns></returns>
        private bool DeleteInSuggestionPrefix(string delete, int deleteLen, string suggestion, int suggestionLen)
        {
            if (deleteLen == 0) return true;
            if (prefixLength < suggestionLen) suggestionLen = prefixLength;
            int j = 0;
            for (int i = 0; i < deleteLen; i++)
            {
                char delChar = delete[i];
                while (j < suggestionLen && delChar != suggestion[j]) j++;
                if (j == suggestionLen) return false;
            }
            return true;
        }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 默认的最大编辑距离，用于字符串相似度计算
        /// <summary>
        /// 从文本中解析出单词
        /// </summary>
        /// <remarks>
        /// 从样本文本创建一个非唯一的词列表
        /// 语言无关（例如，适用于中文字符）
        /// </remarks>
        /// <param name="text"></param>
        /// <returns></returns>
        private string[] ParseWords(string text)
        {
            // \w 字母数字字符（包括非拉丁字符、带变音符号的字符和数字）
            //  "_"不在分割符范围内，尤其组成的术语作为一个单词整体
            // \d 数字
            // 兼容非拉丁字符，不在撇号处分割单词
            MatchCollection mc = Filter.Matches(text.ToLower());

            var matches = new string[mc.Count];
            for (int i = 0; i < matches.Length; i++) matches[i] = mc[i].ToString();
            return matches;
        }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 默认的最大编辑距离，用于字符串相似度计算
        /// <summary>
        ///   返回所有可能的编辑距离为 editDistance 的删除操作
        /// </summary>
        /// <remarks>
        /// 低成本且语言无关：仅删除操作，不包括交换、替换和插入
        /// 替换和插入操作成本高且依赖于语言（例如，中文有 70,000 个 Unicode 汉字）
        /// </remarks>
        /// <param name="word"></param>
        /// <param name="editDistance"></param>
        /// <param name="deleteWords"></param>
        /// <returns></returns>
        private HashSet<string> Edits(string word, int editDistance, HashSet<string> deleteWords)
        {
            editDistance++;
            if (word.Length > 1)
            {
                for (int i = 0; i < word.Length; i++)
                {
                    string delete = word.Remove(i, 1);
                    if (deleteWords.Add(delete))
                    {
                        // 递归，如果尚未达到最大编辑距离
                        if (editDistance < maxDictionaryEditDistance) Edits(delete, editDistance, deleteWords);
                    }
                }
            }
            return deleteWords;
        }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 默认的最大编辑距离，用于字符串相似度计算
        /// <summary>
        /// 返回所有可能的编辑距离为 editDistance 的删除操作
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        private HashSet<string> EditsPrefix(string key)
        {
            HashSet<string> hashSet = new HashSet<string>();
            if (key.Length <= maxDictionaryEditDistance) hashSet.Add("");
            if (key.Length > prefixLength) key = key.Substring(0, prefixLength);
            hashSet.Add(key);
            return Edits(key, 0, hashSet);
        }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 默认的最大编辑距离，用于字符串相似度计算
        /// <summary>
        /// 返回字符串的哈希值
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        private int GetStringHash(string s)
        {
            //return s.GetHashCode();

            int len = s.Length;
            int lenMask = len;
            if (lenMask > 3) lenMask = 3;

            uint hash = 2166136261;
            for (var i = 0; i < len; i++)
            {
                unchecked
                {
                    hash ^= s[i];
                    hash *= 16777619;
                }
            }

            hash &= compactMask;
            hash |= (uint)lenMask;
            return (int)hash;
        }
        #endregion

        #region LookupCompound
        //######################

        // LookupCompound 支持复合词感知的自动拼写纠正，适用于多词输入字符串的三种情况：
        // 1. 在正确单词中错误地插入了空格，导致两个不正确的术语
        // 2. 在两个正确单词之间错误地省略了空格，导致一个不正确的组合术语
        // 3. 多个独立的输入词，可能包含拼写错误

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 默认的最大编辑距离，用于字符串相似度计算
        /// <summary>
        /// 为多词输入字符串查找建议的拼写（支持单词拆分/合并）。
        /// </summary>
        /// <param name="input">要检查拼写的字符串。</param>
        /// <returns>一个 SuggestItem 对象列表，表示输入字符串的建议正确拼写。</returns>
        public List<SuggestItem> LookupCompound(string input)
        {
            return LookupCompound(input, maxDictionaryEditDistance);
        }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 默认的最大编辑距离，用于字符串相似度计算
        /// <summary>查找多词输入字符串的拼写建议（支持单词拆分/合并）。</summary>
        /// <param name="input">被检查拼写的字符串。</param>
        /// <param name="maxEditDistance">输入与建议单词之间的最大编辑距离。</param>
        /// <returns>表示输入字符串拼写建议的 SuggestItem 对象列表。</returns>
        public List<SuggestItem> LookupCompound(string input, int editDistanceMax)
        {
            // 将输入字符串解析为单个词汇
            string[] termList1 = ParseWords(input);
            if (maxDictionaryEditDistance < editDistanceMax) maxDictionaryEditDistance = editDistanceMax + 1;

            List<SuggestItem> suggestions = new List<SuggestItem>();     // 单个词汇的建议
            List<SuggestItem> suggestionParts = new List<SuggestItem>(); // 含有单独部分的一行
            var distanceComparer = new EditDistance(distanceAlgorithm);

            // 将每个词汇转换为其最佳建议，否则保持不变
            bool lastCombi = false;
            for (int i = 0; i < termList1.Length; i++)
            {
                suggestions = Lookup(termList1[i], Verbosity.Closest, editDistanceMax);

                // 组合检查，总是在拆分之前
                if (i > 0 && !lastCombi)
                {
                    List<SuggestItem> suggestionsCombi = Lookup(termList1[i - 1] + termList1[i], Verbosity.Top, editDistanceMax);

                    if (suggestionsCombi.Count > 0)
                    {
                        SuggestItem best1 = suggestionParts[suggestionParts.Count - 1];
                        SuggestItem best2 = new SuggestItem();
                        if (suggestions.Count > 0)
                        {
                            best2 = suggestions[0];
                        }
                        else
                        {
                            // 未知单词
                            best2.term = termList1[i];
                            // 估计的编辑距离
                            best2.distance = editDistanceMax + 1;
                            // 估计的单词出现概率 P=10 / (N * 10^单词长度 l)
                            best2.count = (long)(10 / Math.Pow(10, best2.term.Length));
                            best2.score = distanceComparer.Similarity(best2.term, input);
                        }

                        // distance1= 两个拆分词汇及其最佳修正之间的编辑距离：作为组合的比较值
                        int distance1 = best1.distance + best2.distance;
                        if (distance1 >= 0 && (suggestionsCombi[0].distance + 1 < distance1 || suggestionsCombi[0].distance + 1 == distance1 && suggestionsCombi[0].count > best1.count / (double)Spell.N * best2.count))
                        {
                            suggestionsCombi[0].distance++;
                            suggestionParts[suggestionParts.Count - 1] = suggestionsCombi[0];
                            lastCombi = true;
                            goto nextTerm;
                        }
                    }
                }
                lastCombi = false;

                // 始终拆分没有建议的词汇 / 不拆分编辑距离为 0 的词汇 / 不拆分单字符词汇
                if (suggestions.Count > 0 && (suggestions[0].distance == 0 || termList1[i].Length == 1))
                {
                    // 选择最佳建议
                    suggestionParts.Add(suggestions[0]);
                }
                else
                {
                    // 如果没有完美建议，则将单词拆分为对
                    SuggestItem suggestionSplitBest = null;

                    // 添加原始词汇
                    if (suggestions.Count > 0) suggestionSplitBest = suggestions[0];

                    if (termList1[i].Length > 1)
                    {
                        for (int j = 1; j < termList1[i].Length; j++) {
                            string part1 = termList1[i].Substring(0, j);
                            string part2 = termList1[i].Substring(j);
                            SuggestItem suggestionSplit = new SuggestItem();
                            List<SuggestItem> suggestions1 = Lookup(part1, Verbosity.Top, editDistanceMax);
                            if (suggestions1.Count > 0) {
                                List<SuggestItem> suggestions2 = Lookup(part2, Verbosity.Top, editDistanceMax);
                                if (suggestions2.Count > 0) {
                                    // 选择最佳拆分对建议
                                    suggestionSplit.term = suggestions1[0].term + " " + suggestions2[0].term;
                                    suggestionSplit.score = suggestions2[0].score;
                                    int distance2 = distanceComparer.Compare(termList1[i], suggestionSplit.term, editDistanceMax);
                                    if (distance2 < 0) distance2 = editDistanceMax + 1;

                                    if (suggestionSplitBest != null) {
                                        if (distance2 > suggestionSplitBest.distance) continue;
                                        if (distance2 < suggestionSplitBest.distance) suggestionSplitBest = null;
                                    }

                                    suggestionSplit.distance = distance2;
                                    // 朴素贝叶斯概率：术语合的概率是两个词概率的乘积：P(AB)= P(A) * P(B)
                                    // 使用它来估计组合的频率计数，然后用于排名/选择最佳拆分变体
                                    suggestionSplit.count = (long)(suggestions1[0].count / (double)Spell.N * suggestions2[0].count);

                                    if (suggestionSplitBest == null || suggestionSplit.count > suggestionSplitBest.count) suggestionSplitBest = suggestionSplit;
                                }
                            }
                        }

                        if (suggestionSplitBest != null)
                        {
                            // 选择最佳拆分对建议
                            suggestionParts.Add(suggestionSplitBest);
                        }
                        else
                        {
                            SuggestItem si = new SuggestItem();
                            si.term = termList1[i];
                            // 估计的单词出现概率 P=10 / (N * 10^单词长度 l)
                            si.count = (long)(10 / Math.Pow(10, si.term.Length));
                            si.distance = editDistanceMax + 1;
                            si.score = distanceComparer.Similarity(termList1[i], input);
                            suggestionParts.Add(si);
                        }
                    }
                    else
                    {
                        SuggestItem si = new SuggestItem();
                        si.term = termList1[i];
                        // 估计的单词出现概率 P=10 / (N * 10^单词长度 l)
                        si.count = (long)(10 / Math.Pow(10, si.term.Length));
                        si.distance = editDistanceMax + 1;
                        si.score = distanceComparer.Similarity(termList1[i], input);
                        suggestionParts.Add(si);
                    }
                }
            nextTerm:;
            }

            SuggestItem suggestion = new SuggestItem();

            double count = Spell.N;
            System.Text.StringBuilder s = new System.Text.StringBuilder();
            foreach (SuggestItem si in suggestionParts) { s.Append(si.term + " "); count *= si.count / (double)Spell.N; }
            suggestion.count = (long)count;

            suggestion.term = s.ToString().TrimEnd();
            suggestion.distance = distanceComparer.Compare(input, suggestion.term, int.MaxValue);
            suggestion.score = distanceComparer.Similarity(suggestion.term, input);
            List<SuggestItem> suggestionsLine = new List<SuggestItem>();
            suggestionsLine.Add(suggestion);
            return suggestionsLine;
        }

        #endregion

        #region WordSegmentation

        // WordSegmentation 将字符串分割成单词，在适当的位置插入缺失的空格
        // 拼写错误的单词会被纠正，并不影响分割
        // 已有的空格会被允许并考虑最优分割

        // SymSpell.WordSegmentation 使用了一种非递归的新方法
        // 参考链接: https://seekstorm.com/blog/fast-word-segmentation-noisy-text/
        // 虽然每个长度为 n 的字符串可以被分割成 2^(n-1) 种可能的组合 https://en.wikipedia.org/wiki/Composition_(combinatorics)
        // SymSpell.WordSegmentation 在线性时间 O(n) 内找到最优组合

        // 语料库中所有单词的数量，用于生成频率词典
        // 这个值用于计算单词出现的概率 p 从单词计数 c: p= c / N
        // 如果词典完整，N 等于词典中所有计数 c 的总和；但如果词典被截断或过滤，则不成立
        public static long N { set; get; } = 1024908267229L;

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 默认的最大编辑距离，用于字符串相似度计算
        /// <summary>
        /// 查找多词输入字符串的建议拼写（支持单词拆分/合并）。
        /// </summary>
        /// <param name="input">待检查的字符串。</param>
        /// <returns>
        /// 包含以下四个元素的元组：
        /// 1. 分割后的字符串
        /// 2. 拼写纠正后的字符串
        /// 3. 输入字符串与纠正后字符串之间的编辑距离之和
        /// 4. 单词出现概率的对数和（衡量纠正后分割的常见性和可能性）
        /// </returns>
        public (string segmentedString, string correctedString, int distanceSum, decimal probabilityLogSum) WordSegmentation(string input)
        {
            return WordSegmentation(input, this.MaxDictionaryEditDistance, this.maxDictionaryWordLength);
        }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 默认的最大编辑距离，用于字符串相似度计算
        /// <summary>
        /// 查找多词输入字符串的建议拼写（支持单词拆分/合并）。
        /// </summary>
        /// <param name="input">待检查的字符串。</param>
        /// <param name="maxEditDistance">输入字符串与纠正后单词之间的最大编辑距离
        /// （0 表示仅进行分割，不进行拼写纠正）。</param>
        /// <returns>
        /// 包含以下四个元素的元组：
        /// 1. 分割后的字符串
        /// 2. 拼写纠正后的字符串
        /// 3. 输入字符串与纠正后字符串之间的编辑距离之和
        /// 4. 单词出现概率的对数和（衡量纠正后分割的常见性和可能性）
        /// </returns>
        public (string segmentedString, string correctedString, int distanceSum, decimal probabilityLogSum) WordSegmentation(string input, int maxEditDistance)
        {
            return WordSegmentation(input, maxEditDistance, this.maxDictionaryWordLength);
        }

        // ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // 默认的最大编辑距离，用于字符串相似度计算
        /// <summary>
        /// 查找多词输入字符串的建议拼写（支持单词拆分/合并）。
        /// </summary>
        /// <param name="input">待检查的字符串。</param>
        /// <param name="maxSegmentationWordLength">应考虑的最大单词长度。</param>
        /// <param name="maxEditDistance">输入字符串与纠正后单词之间的最大编辑距离
        /// （0 表示仅进行分割，不进行拼写纠正）。</param>
        /// <returns>
        /// 包含以下四个元素的元组：
        /// 1. 分割后的字符串
        /// 2. 拼写纠正后的字符串
        /// 3. 输入字符串与纠正后字符串之间的编辑距离之和
        /// 4. 单词出现概率的对数和（衡量纠正后分割的常见性和可能性）
        /// </returns>
        public (string segmentedString, string correctedString, int distanceSum, decimal probabilityLogSum) WordSegmentation(string input, int maxEditDistance, int maxSegmentationWordLength)
        {
            if (string.IsNullOrWhiteSpace(input)) return ("", "", 0, 0);

            // v6.7
            // 规范化连字:
            // 将 "scientiﬁc", "ﬁelds", "ﬁnal" 等转换为 "scientific"
            // 使用 Unicode 标准化形式 FormKC，并替换特定字符
            input = input.Normalize(System.Text.NormalizationForm.FormKC).Replace("\u002D", "");

            // 计算数组大小，取输入字符串长度和最大分割词长度中的较小值
            int arraySize = Math.Min(maxSegmentationWordLength, input.Length);

            // 初始化组合数组
            var compositions = new (string segmentedString, string correctedString, int distanceSum, decimal probabilityLogSum)[arraySize];

            // 初始化循环索引
            int circularIndex = -1;

            // 外层循环（列）：遍历所有可能的子串起始位置
            for (int j = 0; j < input.Length; j++)
            {
                // 内层循环（行）：遍历所有可能的子串长度（从起始位置开始）：子串长度不能超过字典中最长的词（除非是未知的长词）
                int imax = Math.Min(input.Length - j, maxSegmentationWordLength);
                for (int i = 1; i <= imax; i++)
                {
                    // 获取子串及其最佳拼写纠正和编辑距离
                    string part = input.Substring(j, i);
                    int separatorLength = 0;
                    int topEd = 0;
                    decimal topProbabilityLog = 0;
                    string topResult = "";

                    if (Char.IsWhiteSpace(part[0]))
                    {
                        // 移除用于 Levenshtein 距离计算的空格
                        part = part.Substring(1);
                    }
                    else
                    {
                        // 增加编辑距离 +1：空格不存在，需要插入
                        separatorLength = 1;
                    }

                    // 移除 part 中的空格，并将移除的空格数量添加到 topEd
                    topEd += part.Length;
                    // 移除 part 中的所有空格
                    part = part.Replace(" ", "");
                    // 将移除的空格数量添加到 topEd
                    topEd -= part.Length;

                    // 查找小写形式的术语建议
                    List<SuggestItem> results = this.Lookup(part.ToLower(), Verbosity.Top, maxEditDistance);
                    if (results.Count > 0)
                    {
                        topResult = results[0].term;

                        // 保留首字母的大写形式
                        if ((part.Length > 0) && Char.IsUpper(part[0]))
                        {
                            char[] a = topResult.ToCharArray();
                            a[0] = char.ToUpper(topResult[0]);
                            topResult = new string(a);
                        }

                        topEd += results[0].distance;
                        // 朴素贝叶斯规则
                        // 假设两个词的概率是独立的
                        // 因此，术语合的概率是这两个词概率的乘积

                        // 为了避免计算概率的乘积，我们计算概率对数的和
                        // 因为词的概率大约为 10^-10，许多这样的小数相乘可能会导致下溢，变成零
                        // log(ab)= log(a) + log(b)
                        topProbabilityLog = (decimal)Math.Log10((double)results[0].count / (double)N);
                    }
                    else
                    {
                        topResult = part;
                        // 默认情况，如果未找到词
                        // 否则长输入文本会作为长未知词获胜（编辑距离为 maxEditDistance + 1），尽管应该插入许多空格
                        topEd += part.Length;
                        topProbabilityLog = (decimal)Math.Log10(10.0 / (N * Math.Pow(10.0, part.Length)));
                    }

                    int destinationIndex = ((i + circularIndex) % arraySize);

                    // 在第一次循环中设置初始值
                    if (j == 0)
                    {
                        compositions[destinationIndex] = (part, topResult, topEd, topProbabilityLog);
                    }
                    else if ((i == maxSegmentationWordLength)
                            // 如果概率更高，且编辑距离相同或相差一个空格
                            || (((compositions[circularIndex].distanceSum + topEd == compositions[destinationIndex].distanceSum)
                                || (compositions[circularIndex].distanceSum + separatorLength + topEd == compositions[destinationIndex].distanceSum))
                                && (compositions[destinationIndex].probabilityLogSum < compositions[circularIndex].probabilityLogSum + topProbabilityLog))
                            // 如果编辑距离更小
                            || (compositions[circularIndex].distanceSum + separatorLength + topEd < compositions[destinationIndex].distanceSum))
                    {
                        // v6.7
                        // 保持标点符号或撇号与前一个词相邻
                        if (((topResult.Length == 1) && char.IsPunctuation(topResult[0]))
                            || ((topResult.Length == 2) && topResult.StartsWith("’")))
                        {
                            compositions[destinationIndex] = (
                            compositions[circularIndex].segmentedString + part,
                            compositions[circularIndex].correctedString + topResult,
                            compositions[circularIndex].distanceSum + topEd,
                            compositions[circularIndex].probabilityLogSum + topProbabilityLog);
                        }
                        else
                        {
                            compositions[destinationIndex] = (
                            compositions[circularIndex].segmentedString + " " + part,
                            compositions[circularIndex].correctedString + " " + topResult,
                            compositions[circularIndex].distanceSum + separatorLength + topEd,
                            compositions[circularIndex].probabilityLogSum + topProbabilityLog);
                        }
                    }
                    else
                    {

                    }

                }
                circularIndex++; if (circularIndex == arraySize) circularIndex = 0;
            }
            return compositions[circularIndex];
        }
        #endregion
    }
}
